import re
#定义栈数据结构
class Stack(object):
    # 初始化栈为空列表
    def __init__(self):
        self.items = []
    # 判断栈是否为空，返回布尔值
    def is_empty(self):
        return self.items == []
    # 返回栈顶元素
    def peek(self):
        return self.items[len(self.items) - 1]
    # 返回栈的大小
    def size(self):
        return len(self.items)
    # 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）
    def push(self, item):
        self.items.append(item)
    # 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）
    def pop(self):
        return self.items.pop()
    def items(self):
        return self

#栈的使用方法
#     # 初始化一个栈对象
#     my_stack = Stack()
#     # 把'h'丢进栈里
#     my_stack.push('h')
#     # 把'a'丢进栈里
#     my_stack.push('a')
#     # 看一下栈的大小（有几个元素）
#     print(my_stack.size())
#     # 打印栈顶元素
#     print(my_stack.peek())
#     # 把栈顶元素丢出去，并打印出来
#     print(my_stack.pop())
#     # 再看一下栈顶元素是谁
#     print(my_stack.peek())
#     # 这个时候栈的大小是多少？
#     print(my_stack.size())
#     # 再丢一个栈顶元素
#     print(my_stack.pop())
#     # 看一下栈的大小
#     print(my_stack.size)
#     # 栈是不是空了？
#     print(my_stack.is_empty())
#     # 哇~真好吃~
#     print('Yummy~')
#定义运算符优先级
ops_level = {
    '+':1,
    '-':1,
    '*':2,
    '/':2,
    '(':100,
    ')':100,
}
#定义运算
def cal(n1, n2, op):
    #因为需要考虑小数，所以全部转换成为浮点数
    n1 = float(n1)
    n2 = float(n2)
    if op == '+':
        # print('+法',n1 + n2)
        return n1 + n2

    if op == '-':
        # print('-法',n1 - n2)
        return n1 - n2

    if op == '*':
        # print('乘法',n1,n2,n1 * n2)
        return n1 * n2

    if op == '/':
    #     print('除法',n1 / n2)
        return n1 / n2


#将字符串转换成为按照运算符和括号区分的列表
cal_string = '100/(1+25-1)*3+25/(0-25)-100'
#re匹配
cal_strings = re.split('(\+|\-|\*|\/|\(|\))',cal_string.strip())
#使用filter过滤器
cal_string_list = [item for item in filter(lambda x: x!='',cal_strings)]

if __name__ == '__main__':
#临时存储运算符的栈expression_stack（含一个结束符号），一个作为输入逆波兰式的栈operator_stack（空栈）
#整体逻辑
# 1.如果是运算数直接压入operator_stack (else )
# 1.如果是运算符
#     1（直接压入
#     2.）(之间的运算符，逐个出栈，依次压入栈expression_stack
#     3.如果不是（、）、则判断栈顶元素为（则直接压入，不是则判断。如果小于优先级，直接将其压入expression_stack。直到优先级大于等于栈顶元素
# 2.遍历完以后检查operator_stack是否为空，不为空则全部压入expression_stack
#operator_stack 运算符栈
#expression_stack 表达式栈，数字直接入栈
    operator_stack = Stack()
    expression_stack = Stack()
#遍历字符串
    for i in range(0,len(cal_string_list)):
#如果是左括号直接压入operator_stack
        if cal_string_list[i] == '(':
            operator_stack.push(cal_string_list[i])
#如果是右括号，则找到最近的左括号出栈，并且进入表达式栈
        elif cal_string_list[i] == ')':
            while operator_stack.size() > 0:
                operator_stackpop = operator_stack.pop()
                if operator_stackpop == '(':
                    break
                else:

                    expression_stack.push(operator_stackpop)




        elif cal_string_list[i] in ['+','-','*','/']:
            #print(cal_string_list[i])
            if operator_stack.size() > 0:
                #如果栈顶运算符为括号，或者，栈顶运算符的优先级小于当前运算符优先级直接入栈
                if operator_stack.peek() == '(' or ops_level[operator_stack.peek()] < ops_level[cal_string_list[i]]:
                    operator_stack.push(cal_string_list[i])
                    # print('charu',cal_string_list[i])
                    # print(operator_stack.items)


                #运算符小于或者等于栈顶元素。将操作符出栈、并且，按照规矩入栈。（直到当前运算符的大于不等于栈顶运算）完成后将，当前运算符入运算符栈
                else:
                    while operator_stack.size()>0 and ops_level[operator_stack.peek()] >= ops_level[cal_string_list[i]] :
                        operator_stackpop = operator_stack.pop()
                        if operator_stackpop == '(':
                            operator_stack.push('(')
                            break
                        else:
                            expression_stack.push(operator_stackpop)
                    operator_stack.push(cal_string_list[i])#当前运算符入运算符栈


            else:

                operator_stack.push(cal_string_list[i])
        else:

            expression_stack.push(cal_string_list[i])
    #判断运算符栈是否为空，不为则将其全部出栈进栈到表达式栈
    if operator_stack.size() == 0:
        print(expression_stack.items)
    else:

        while operator_stack.size() > 0:
            operator_stack_pops = operator_stack.pop()
            expression_stack.push(operator_stack_pops)
        print('原表达式 :',cal_string)
        print('逆波兰表达式 Polish Notation：',expression_stack.items)#表达式栈即结果

#运算。
#数字栈，到了运算符，取栈顶两元素计算，计算完成入栈，最后栈元素即结果
    reads = expression_stack.items
    cal_result_stack = Stack()
    for i in reads:
        #判断是否是数字
        if i.isdigit() == True:
            cal_result_stack.push(i)
        else:
            #print(cal_result_stack.items)
            if cal_result_stack.size() > 1 :
                a = float(cal_result_stack.pop())
                b = float(cal_result_stack.pop())
                #此处注意运算顺序问题
                cal_result = cal(b,a,i)
                cal_result_stack.push(cal_result)
                print('计算结果入栈数字', cal_result_stack.peek())

